#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
拓扑排序可以尾巴开始处理(没有neighbors的节点就是尾巴)
也可以从头处理(没有前驱节点: 但是头节点不容易寻找, 不像尾巴只用判断neighbors field即可)

关联题目: ./q1366-directed-graph-loop.py
"""

from collections import defaultdict


class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []


class Solution:
    # 利用入读为0 作为头(本质上是一种广度有限算法)
    def topSort(self, graph):
        return self.top_sort_kahn(graph)

    # =================== kahn算法 =====================
    def top_sort_kahn(self, graph):
        # graph: node list, 是以节点和节点邻接节点为主存储
        # 还有一种存法是存储每条边, 以边为主表示图
        self.graph = graph
        self.stack = []
        self.edges_num = 0
        self.in_degree = defaultdict(int)         # 记录节点入度
        self.build_in_degree()
        self.zero_in_degree_nodes = self.find_zero_degree()     # 广度有限搜索的队列!!!

        while self.zero_in_degree_nodes:
            # 广度拓扑排序
            node = self.zero_in_degree_nodes.pop()
            self.stack.append(node)

            for nei in node.neighbors:
                self.in_degree[nei] -= 1
                self.edges_num -= 1
                if self.in_degree[nei] == 0:
                    self.zero_in_degree_nodes.append(nei)

        # 判定是否有环
        assert self.edges_num == 0
        return self.stack

    def build_in_degree(self):
        for node in self.graph:
            self.in_degree[node]        # NOTE: 访问defaultdict, 把node添加进入

            for nei in node.neighbors:
                self.in_degree[nei] += 1
                self.edges_num += 1

    def find_zero_degree(self):
        ret = []
        for node, in_degree in self.in_degree.items():
            if in_degree == 0:
                ret.append(node)
        return ret


class Solution2:
    '''
    使用DFS: 深度搜索解决该问题(前提: 有向无环图, 不能出现环)
    环状也不可能存在"拓扑排序"
    DFS本质上也是寻找出度为0的尾巴元素, 然后再向上倒退

    NOTE: 当然这里也可以加入tarjan算法的stack, 去判断图中是否存在环!

    BFS需要graph方向不会跨层才可以使用(第2层节点不会指向第2层节点, 第3层节点不会指向第2层节点)
    '''
    def topSort(self, graph):
        # graph 是 Node list

        self.stack = []
        self.ready_to_handles = set(graph)      # 还没有被处理的节点: 如果处理过后, 从ready_to_handles中删除

        while self.ready_to_handles:
            # node = self.get_from_set(self.ready_to_handles)
            # self.top_sort_node(node)
            node = self.ready_to_handles.pop()         # 在处理子节点前就删除了, 那么在递归处理子节点时: 也要提前判断, 再处理子节点
            self.top_sort_node(node)

        return self.stack

    def top_sort_node(self, node):
        # if node not in self.ready_to_handles:            # 比如0的孩子有(1, "2", 3), 1的孩子有("2", 4, 5), 这样2会在处理1时先处理(深度优先)
        #     return
        # self.ready_to_handles.remove(node)

        for child in node.neighbors:
            if child in self.ready_to_handles:
                self.ready_to_handles.remove(child)
                self.top_sort_node(child)

        self.stack.insert(0, node)

    def get_from_set(self, input_set):
        # 获取一个元素, 但不从set中删除
        return next(iter(input_set))
        # ele = input_set.pop()
        # input_set.add(ele)
        # return ele


class Solution3:
    '''
    出度: outdegree, 即从尾巴开始处理
    一个不好的解决方案: 之所以可以Accept, 是因为系统只检查了返回值中的对象id, 没有查看对象内容是否改变
    这里使用出度解决的, 一个更好的解决方案是使用入度
    '''
    def topSort(self, graph):
        self.stack = []
        self.graph = graph
        while graph:
            idx, tail = self.get_one_tail()     # NOTE: slow 需要遍历
            self.stack.insert(0, tail)
            self.graph_delete(idx, tail)        # NOTE: slow 需要遍历

        return self.stack

    def get_one_tail(self):
        for i, node in enumerate(self.graph):
            if not node.neighbors:
                return i, node

        assert False

    def graph_delete(self, idx, tail):
        del self.graph[idx]     # NOTE: 改变了graph

        for node in self.graph:
            if tail in node.neighbors:
                node.neighbors.remove(tail)     # NOTE: 改变了node



def main():
    print("start main")
    l5 = DirectedGraphNode(5)
    l4 = DirectedGraphNode(4)
    l3 = DirectedGraphNode(3)
    l3.neighbors = [l4, l5]
    s = Solution()
    ret = s.topSort([l3, l4, l5])
    print(ret[0].label)
    print(ret[1].label)
    print(ret[2].label)


if __name__ == "__main__":
    main()
